package com.cobla.struct.map;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * 邻接矩阵
 */
@NoArgsConstructor
@Data
public class MatrixMap {
    /**
     * edges 边<br/>
     * n 顶点个数<br/>
     * e 边个数<br/>
     * vexs 顶点集合<br/>
     */
    private int edges[][];
    private int n, e;
    private Vertex[] vexs;

    public MatrixMap(int vexMax, int[]... linkedEdges) {
        this.vexs = new Vertex[vexs.length];
        for (int i = 0; i < vexMax; i++) {
            this.vexs[i] = new Vertex(i);
        }
        n = vexs.length;
        this.edges = new int[n][n];
        // 链接边
        linkVertex(linkedEdges);
    }

    /**
     * 设置边<br/>
     * 每个数组只能是2个或者3ge大小，不多不少<br/>
     * 数组代表从顶点到顶点的链接关系<br/>
     * 例如<br/>
     * [2, 7], [4, 1]<br/>
     * 代表边从2到7，边从4到1<br/>
     * [1, 8, 3], [3, 6, 10]代表边1到8权值为3，边3到6权值为10<br/>
     */
    public void linkVertex(int[]... linkedEdges) throws RuntimeException {
        for (int i = 0; i < linkedEdges.length; i++) {
            int[] linkedEdge = linkedEdges[i];
            int from = 0;
            int to = 0;
            int weight = 1;
            assert linkedEdge.length == 2||linkedEdge.length == 3;
            if (linkedEdge.length == 2) {
                from = linkedEdge[0];
                to = linkedEdge[1];
            } else if (linkedEdge.length == 3) {
                from = linkedEdge[0];
                to = linkedEdge[1];
                weight = linkedEdge[2];
            }
            this.edges[from][to] = weight;
        }
    }

    /**
     * 普里姆算法，从代码上看只能是带权图了
     * @param map
     * @param v0 最开始选择的点
     * @return
     */
    public int prim(MatrixMap map, int v0){
        // 点数，矩阵大小
        int n = map.n;
        // lowcost 当前并入的点形成的图 到 其他剩余点的距离（一个点多个距离的话取最小的那个）
        // vset 已经并入的点
        int[] lowcost = new int[n], vset = new int[n];
        // 当前点
        int v = v0;
        for (int i = 0; i < map.n; i++) {
            // 最开始的点到其他点的距离
            lowcost[i] = map.edges[v][i];
            vset[i] = 0;
        }
        vset[v] = 1;
        int sum = 0;
        int k = v;
        int min = Integer.MAX_VALUE;
        // 从剩余的 n-1 个点中取点
        for (int i = 0; i < map.n - 1; i++) {
            min = Integer.MAX_VALUE;
            // 计算当前 j 点到其他点的距离，选择还没有并入vset并且边值最小的那个
            for (int j = 0; j < map.n; j++) {
                if (vset[j] == 0 && lowcost[j] < min) {
                    // mark point
                    min = lowcost[j];
                    k = j;
                }
            }
            // 并入生成树
            vset[k] = 1;
            v = k;
            sum += min;
            for (int j = 0; j < map.n; j++) {
                if (vset[j] == 0 && lowcost[j] > map.edges[v][j]) {
                    lowcost[j] = map.edges[v][j];
                }
            }
        }
        return sum;
    }

}

@Data
@AllArgsConstructor
class Vertex {
    /**
     * 顶点编号，必须有
     */
    private int no;
}
